package com.yequan.leetcode.linkedlist.reverselist_206;

import com.yequan.leetcode.linkedlist.ListNode;

/**
 * //反转一个单链表。
 * //
 * // 示例:
 * //
 * // 输入: 1->2->3->4->5->NULL
 * //输出: 5->4->3->2->1->NULL
 * //
 * // 进阶:
 * //你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * // Related Topics 链表
 *
 * @author : Administrator
 * @date : 2020/3/16
 */
public class ReverseList {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.addNode(listNode, 2);
        listNode.addNode(listNode, 3);
        listNode.addNode(listNode, 4);
        listNode.addNode(listNode, 5);

        ReverseList reverseList = new ReverseList();
        ListNode listNode1 = reverseList.reverseList5(listNode);
        ListNode currentNode = listNode1;
        while (currentNode != null) {
            System.out.println(currentNode.val);
            currentNode = currentNode.next;
        }
    }

    /**
     * 遍历+逐个反转(迭代法)
     * 核心思想:
     * 在链表遍历过程中,将每一个链表节点的next指针都指向前一个节点
     * 复杂度:
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     *
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {

        ListNode preNode = null;
        ListNode currentNode = head;
        while (null != currentNode) {
            ListNode tempNode = currentNode.next;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = tempNode;
        }
        return preNode;
    }

    public ListNode reverseList2(ListNode head) {
        ListNode preNode = null;
        ListNode currentNode = head;
        while (null != currentNode) {
            //第二个节点
            ListNode tempNode = head.next;
            //头结点指向空
            currentNode.next = preNode;
            //前一个节点指向头结点
            preNode = currentNode;
            //当前节点指向第二个节点
            currentNode = tempNode;
        }
        return preNode;
    }

    public ListNode reverseList3(ListNode head) {
        ListNode preNode = null;
        ListNode currentNode = head;
        while (null != currentNode) {
            ListNode nextNode = currentNode.next;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = nextNode;
        }
        return preNode;
    }

    public ListNode reverseList4(ListNode head) {
        ListNode preNode = null;
        ListNode currentNode = head;
        while (null != currentNode) {
            ListNode nextNode = currentNode.next;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = nextNode;
        }
        return preNode;
    }

    public ListNode reverseList5(ListNode head) {
        ListNode preNode = null;
        ListNode currentNode = head;
        while (null != currentNode) {
            ListNode nextNode = currentNode.next;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = nextNode;
        }
        return preNode;
    }

    public ListNode reverseList6(ListNode head) {
        ListNode preNode = null;
        ListNode currentNode = head;
        while (null != currentNode) {
            ListNode next = currentNode.next;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = next;
        }
        return preNode;
    }
}
